using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using 数据挖掘实验.Logger;

namespace 数据挖掘实验
{
    public class AprioriItem : IEnumerable<AprioriItem>
    {
        int total; // 样本总数
        AprioriItem prior; // 前一个节点
        Dictionary<int, AprioriItem> nextDic = new Dictionary<int, AprioriItem>(); // 下一个节点
        public int Key { get; }
        public int Count { get; private set; }
        public float Support => (float) Count / total;
        public int Depth { get; private set; }

        public ConfidenceCollector ConfidenceCollector { get; }

        public AprioriItem(int key)
        {
            ConfidenceCollector = new ConfidenceCollector();
            Key = key;
        }

        /// <summary>
        /// 累计包含所有项的数目
        /// </summary>
        /// <param name="entries">所有项集</param>
        void Accumulate(List<HashSet<int>> entries)
        {
            foreach (var entry in entries)
            {
                bool flag = true; // 是否包含所有项
                AprioriItem item = this;
                do
                {
                    if (!entry.Contains(item.Key)) // 如果不包含某个项就跳出
                    {
                        flag = false;
                        break;
                    }
                } while ((item = item.prior) != null);

                if (flag) // 包含所有项时进行累加
                    Count++;
            }
        }

        /// <summary>
        /// 计算所有的置信度
        /// </summary>
        /// <param name="aprioriCollector"></param>
        /// <param name="confidenceThreshold"></param>
        public void ComputeConfidence(AprioriCollector aprioriCollector, List<string> transaction,
            float confidenceThreshold)
        {
            List<int> itemList = GetIndexStack().ToList(); // 获取该到从AprioriController到该节点的所有下标
            for (int startPos = 0; startPos < itemList.Count; startPos++)
            {
                ConfidenceCollector.Collect(startPos, itemList, aprioriCollector, transaction,
                    confidenceThreshold);
            }
        }

        public bool ComputeSupport(int startPos, int depth, AprioriCollector collector,
            Queue<Action> pendingComputeTask,
            List<string> transaction,
            IEnumerable<int> continuousSectionIndex,
            List<HashSet<int>> entries,
            float supportThreshold)
        {
            Depth = depth;
            if (startPos > transaction.Count) // 是否已经是最后一个项
                return false;

            if (!DetectSelfJoin(collector, depth)) // 检查是否自连接
                return false;

            total = entries.Count; // 记录项集总数
            Accumulate(entries); // 累计出现的次数

            if (Support < supportThreshold) // 如果支持度未达到阈值返回false
                return false;
            LogManager.AprioriLogger.Log($"计算出{GetFormulaString(transaction)}");

            IEnumerable<int> candidate = continuousSectionIndex;
            if (TryGetPrior(out var priorItem))
                if (priorItem.TryGetPrior(out priorItem))
                    candidate = priorItem.nextDic.Keys;

            foreach (var i in candidate)
            {
                if (i < Key)
                    continue;
                var index = i;
                pendingComputeTask.Enqueue(() => // 广度计算解决方案 任务队列
                {
                    var next = new AprioriItem(index) {prior = this};
                    if (next.ComputeSupport(index + 1, depth + 1, collector, pendingComputeTask, transaction,
                        continuousSectionIndex, entries,
                        supportThreshold))
                        nextDic[index] = next;
                    else
                        next.prior = null;
                });
            }

            return true;
        }

        bool DetectSelfJoin(AprioriCollector collector, int depth)
        {
            if (depth <= 1) // 第一层默认是自连接的
                return true;

            HashSet<int> indexSet = GetIndexStack().ToHashSet();

            var childrenStack = new Stack<AprioriItem>();
            foreach (var key in collector.Keys)
            {
                AprioriItem item;
                item = collector[key];
                if (item.Depth == depth - 1)
                    childrenStack.Push(item);
                foreach (var tailItem in item)
                    if (tailItem.Depth == depth - 1)
                        childrenStack.Push(tailItem);
            }

            int num = 0; // 计数 需要保证与至少包含上一深度列表C(深度-1)_(深度)个条目
            int expect = Cmn(depth - 1, depth); // C(深度-1)_(深度)
            while (childrenStack.TryPop(out var item))
            {
                bool contain = true;
                do
                {
                    if (!indexSet.Contains(item.Key))
                    {
                        contain = false;
                        break;
                    }
                } while ((item = item.prior) != null);

                if (contain) // 当前item的深度和计算深度正好相差一 且包含整个条目
                    num++;
            }

            return num >= expect;
        }

        /// <summary>
        /// 组合数
        /// </summary>
        /// <param name="m">上标</param>
        /// <param name="n">下标</param>
        /// <returns></returns>
        int Cmn(int m, int n)
        {
            if (m == 0)
                return 1;
            int ele = 1;
            int div = 1;
            for (var i = 0; i < m; i++)
                ele *= n--;

            for (int i = 0; i < m; i++)
                div *= m--;

            return ele / div;
        }

        public AprioriItem this[int key]
        {
            get
            {
                if (nextDic.TryGetValue(key, out var item))
                    return item;
                return null;
            }
        }

        /// <summary>
        /// 获取索引栈
        /// </summary>
        /// <returns>索引栈</returns>
        public Stack<int> GetIndexStack()
        {
            var stack = new Stack<int>();
            AprioriItem item = this;
            do
            {
                stack.Push(item.Key);
            } while ((item = item.prior) != null);

            return stack;
        }


        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<AprioriItem> GetEnumerator()
        {
            var childrenQueue = new Queue<Dictionary<int, AprioriItem>>();
            childrenQueue.Enqueue(nextDic);

            while (childrenQueue.TryDequeue(out var children))
            {
                foreach (var child in children.Values)
                {
                    childrenQueue.Enqueue(child.nextDic);
                    yield return child;
                }
            }
        }

        public bool TryGetPrior(out AprioriItem priorItem)
        {
            if (prior == null)
            {
                priorItem = null;
                return false;
            }

            priorItem = prior;
            return true;
        }

        public string GetFormulaString(List<string> formList)
        {
            var builder = new StringBuilder();
            var item = this;
            var indexStack = new Stack<int>();
            builder.Append("Support(");
            while (item.TryGetPrior(out item))
                indexStack.Push(item.Key);

            while (indexStack.TryPop(out var index))
            {
                builder.Append(formList[index]);
                if (indexStack.Count > 0)
                    builder.Append(',');
            }

            if (this.prior != null)
                builder.Append("=>");
            builder.Append(formList[this.Key]).Append(")=").Append(Support);

            return builder.ToString();
        }

        public string GetItemsStr(List<string> formList)
        {
            var item = this;
            var indexStack = new Stack<string>();
            do
            {
                indexStack.Push(formList[item.Key]);
            } while (item.TryGetPrior(out item));

            return string.Join(",", indexStack);
        }
    }
}